import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 084. 含有重复元素集合的全排列
 * @author: WXY
 * @create: 2023-01-04 21:51
 * @Version 1.0
 * <p>
 * 出错了，这个题目提交错误，重复添加了相同的 list
 **/
public class Num_offer2_084_permuteUnique {
    public static List<List<Integer>> permuteUnique(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new ArrayList<>();
        }
        List<List<Integer>> all = new ArrayList<>();
        process(arr, 0, all);
        return all;
    }

    private static void process(int[] arr, int i, List<List<Integer>> all) {
        if (i == arr.length) {
            all.add(Arrays.stream(arr).boxed().collect(Collectors.toList()));
            return;
        }
        boolean[] visit = new boolean[21];
        for (int j = i; j < arr.length; j++) {
            if (!visit[arr[j] + 10]) {
                visit[arr[j] + 10] = true;
                swap(arr, i, j);
                process(arr, i + 1, all);
                swap(arr, i, j);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2};
        List<List<Integer>> lists = permuteUnique(arr);
        System.out.println(lists);
    }
}
